Search results for "graph labeling"

Radio Labelings of Distance Graphs

2013

A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.

Radio k-Labelings for Cartesian Products of Graphs

2005

International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…

Application of graph grammars in music composing systems

1987

The radio antipodal and radio numbers of the hypercube

2011

International audience; A radio k-labeling of a connected graph G is an assignment f of non negative integers to the vertices of G such that |f(x) − f(y)| \ge k + 1 − d(x, y), for any two vertices x and y, where d(x, y) is the distance between x and y in G. The radio antipodal number is the minimum span of a radio (diam(G) − 1)-labeling of G and the radio number is the minimum span of a radio (diam(G))-labeling of G. In this paper, the radio antipodal number and the radio number of the hypercube are determined by using a generalization of binary Gray codes.